<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>哈希表</title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	/*
	哈希表介绍：
		是最高效的查找算法
		哈希表通常是基于数组进行实现的，但是相对于数组，它也有很多优势：
			它可以提供非常快速的插入-删除-查找操作
			无论多少数据，插入和删除值需要接近常量的时间：即O（1）的时间。实际上，只需要几个机器指令即可完成
			哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
			哈希表相对于树来说编码要容易很多
		哈希表相对于数组的一些不足：
			哈希表中的数据时没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。
			通常情况下，哈希表的key是不允许重复的，不能放置相同的key,用于保存不同的元素。
			
	哈希表的概念：
			哈希化：将大数字转化成数组范围内下标的过程，我们就称之为哈希化。
			哈希函数：通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数我们称为哈希函数。
			哈希表：最终将数据插入到的这个数组，对真个结构的封装，我们就称之为是一个哈希表。
	
	需要解决的问题：
			虽然，我们在一个1000000的数组中，放50000个单词已经足够，但是
			通过哈希化后的下标值依然可能会重复，如何解决这种重复的问题呢？
			
		解决方法：
		1.链地址法:是一种比较常见的解决冲突的方案（也称拉链法）
		  解析：
			链地址法解决冲突的办法是每个数组单元A中存储的不再是单个数据，而是一个链条。
			这个链条使用什么数据结构呢？常见的是数组或者链表。
			比如是链表，也就是每个数组单元中存储这一个链表，一旦发现重复，将重复的元素插入到链表的首段或者末端即可。
			当查询是，先根据哈希化后的下标值找到对应的位置，再取出链表，一次查询找寻找的数据。
		  选择数据还是链表？
			数组或者链表在这里其实都可以，效率上也差不多。
			因为根据哈希华的index找到这个数组或者链表是，通常就会使用线性查找，这个时候数组和链表的效率是差不多的。
			在某些实现中，会将新插入的数据放在数组或者链表的最前面，因为觉得新插入的数据用于取出的可能性更大。
			这个也是要根据也为需要，不见得新的数据就访问次数会更多，：比如新添加的好友。
			
		2.开放地址法：寻找空白的单元格来添加重复的数据
		  解析：
			开发地址法其实就是要寻找空白的位置来放置冲突的数据项
		  探索位置的方式：
			1.线性探测
				问题：
					如果之前插入的数据时连续的，那么新插入的数据可能需要探测很长的距离
					线性探测有一个比较严重的问题，那就是聚集，什么叫做聚集呢
					比如我在没有任何数据的时候，插入的是22-23-24-25-26，那么意味着下标值：2-3-4-5-6的位置都有元素
					这种一连串填充单元就叫做聚集
					聚集会影响哈希表的性能，无论是插入/查询/删除都会有影响。
					比如我们插入一个32，会发现连续的单元都不允许我们放置数据，并且在这个过程中我们需要探索多次。
					二次探测可以解决一部分这个问题。
			2.二次探测
				优化：
					二次探测主要优化的是探测时的步长，
					线性探测，我们可以看成是步长为1的探测，比如从下标值x开始，那么线性探测就是x+1,x+2,x+3一次探测
					二次探测，对步长进行了优化，比如从下标值x开始，x+1^2,x+2^2,x+3^2
					那么这样就可以一次性探测比较长的距离，避免那些聚集带来的影响。
				问题：
					但是二次探测依然会存在一些问题，比如我们插入的数据是32-112-82-2-192，那么它们依次累加的时候步长是相同的。
					也就是这种情况下会照成步长不一的一种聚集，还是会影响效率。（当然这种可能性相对于连续的数字会小一些）
					怎么根本解决这个问题呢？让每个人的步长都不相同。
			3.再哈希法
				 二次探测的算法产生的探测序列步长是固定的：1，4,9,16，依次类推。
				 现在在需要一种方法：产生一种依赖关键字的探测序列，而不是每个关键字都一样。
				 那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。
				 再哈希法的做法就是：把关键字用另外一个哈希函数，再做一次哈希化，用这次哈希化的结果作为步长。
				 对于指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。
			  第二次哈希化需要具备如下特点：
				和第一个哈希函数不同。（不要再使用上一次的哈希函数了，不然结果还是原来的位置）
				不能输入为0（否则，将没有步长。每次探测都是原地踏步，算法就进入了死循环）
			  其实，我们不要费脑细胞来设计，计算机专家已经设计出一种工作很好的哈希函数：
				stepSize = constant - (key & constant )
				其中constant是质数，且小于数组的容量.
				例如：stepSize = 5 - (key & 5)，满足需求，并且结果不可能为0.
				   
	------------------------------------------------哈希化的效率-------------------------------------------------------------------
		哈希表中执行插入和搜索操作效率是非常高的
			如果没有产生冲突，那么效率就会更高。
			如果发送冲突，存取时间就会依赖后来的探测长度。
			平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度也越来越长。
			随着填装因子变大，效率下降的情况，在不同开放地址法方案中比链地址法更严重，所以我们来对比一下他们的效率，再决定
			我们的选取的方案。
		在分析效率之前，我们先了解一个概念：填装因子.
			填装因子表示当前哈希表中已经包含的数据项和真个哈希表长度的比值。
			填装因子=总数据项/哈希表长度
			开放地址法的填装因子最大是多少呢？1，因为它必须寻找到空白的单元才能将元素放入。
			链地址法的填装因子呢？可以大于1，因为拉链法可以无限的延伸下去，只要你愿意。（后面的效率就变低了）
			
		1.二次探测和再哈希化：	
		线性探测时，探测序列（P）和填装因子（L）的关系
			对成功的查找：P=（1+1/（1-L）^2）2
			对不成功的查找:P=(1+1/(1-L))2
		解析：
			当填装因子是1/2是，成功的搜索需要1.5次比较，不成功的搜索需要2.5次
			当填装因子为2/3时，分别需要2.0次和5.0次比较
			如果填装因子更大，比较次数会非常大
			应该使填装因子报错在2/3以下，最好在1/2以下，另一方面，填装因子越低，对于给定数量的数据项，就需要越多的空间。
			实际情况中，最好的填装因子取决于存储效率和速度之间的平衡，随着填装因子变小，存储效率下降，而速度上升。
		
		2.链地址法：
			不会因为添加某元素后性能急剧下降。
			比如Java的HashMap中使用的就是链地址法。
	-------------------------------------优秀的哈希函数---------------------------------------------------------		哈希函数：
		好的哈希函数应该尽可能让计算的过程变得简单，提高计算的效率
			哈希表的主要优点是它的速度，所以在速度上不能满足，那么就不能达到设计的目的了。
			提高速度的一个办法就是让哈希函数中尽量少的有乘法和除法，因为他们的性能比较低的
	设计好的哈希函数应该具备哪些优点？
		1.快速的计算
			哈希表的优势就在于效率，所以快速获取到对应的hashCode非常重要。
			需要通过快速的计算来获取到元素对应的hashCode
		2.均匀的分布
			哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置的时候，都会影响效率。
			优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀的分布
	快速计算：霍纳法则
			
	均匀分布：
		在设计哈希表时，我们已经有办法处理映射到相同下标值的情况，链地址法或开放地址法。
		但是无论哪种方案，为了提供效率，最好的情况还是让数据在哈希表中均匀分布。
		因此我们需要在使用常量的地方，尽量使用质数。
		质数的使用：
			哈希表的长度。
			N次幂的底数（）
			哈希表的长度最好使用质数。
		再哈希法中质数的重压使用，
	*/
</script>
